package com.example.algorithm.no0198.solution;

import com.example.algorithm.no0198.Solution;

/**
 * @Description 动态规划
 * 时间复杂度 O(N) ： 遍历 nums 需要线性时间；
 * 空间复杂度 O(1) ： cur和 pre 使用常数大小的额外空间。
 * @ClassName DpSolution
 * @Author Administrator
 * @Date 2020/5/16 12:48
 * @Version 1.0.0
 */
public class RollSolutionImpl implements Solution {

    /**
     * {1,2,3,1}   4
     *
     * @param nums {1,2,3,1}
     */
    @Override
    public int rob(int[] nums) {

        if (nums == null || nums.length == 0) {
            return 0;
        }

        int size = nums.length;
        if (size == 1) {
            return nums[0];
        }

        int pre = 0;
        int cur = 0;
        int temp = 0;

        for (int num : nums) {
            temp = cur;
            cur = Math.max(pre + num, cur);
            pre = temp;
        }

//        pre = nums[0];
//        cur = Math.max(nums[0], nums[1]);
//        for (int i = 2; i < size; i++) {
//            temp = cur;
//            cur = Math.max(cur, pre + nums[i]);
//            pre = temp;
//        }

        return cur;
    }
}
